package com.peng.leetcode.array;

/**
 * SearchMatrix
 * <p>
 * 240. 搜索二维矩阵 II
 *
 * @author: lupeng6
 * @create: 2021/3/19 14:01
 */
public class SearchMatrix1 {

    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        System.out.println(new SearchMatrix1().searchMatrix(matrix, 5));
    }


    /**
     * 使用二分法查找指定数据
     *
     * @author lupeng6
     * @date 2021/3/22 10:55
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int min = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < min; i++) {
            boolean rowFlag = binarySearch(matrix, i, target, true);
            boolean colFlag = binarySearch(matrix, i, target, false);
            if (rowFlag || colFlag) {
                return true;
            }
        }
        return false;
    }

    private boolean binarySearch(int[][] matrix, int start, int target, boolean isRow) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        if (isRow) {
            int end = rows - 1;
            int rowStart = start;
            while (rowStart <= end) {
                int mid = (rowStart + end) / 2;
                if (matrix[mid][start] == target) {
                    return true;
                } else if (matrix[mid][start] > target) {
                    end = mid - 1;
                } else if (matrix[mid][start] < target) {
                    rowStart = mid + 1;
                }
            }
        } else {
            int end = cols - 1;
            int colStart = start;

            while (colStart <= end) {
                int mid = (colStart + end) / 2;
                if (matrix[start][mid] == target) {
                    return true;
                } else if (matrix[start][mid] > target) {
                    end = mid - 1;
                } else if (matrix[start][mid] < target) {
                    colStart = mid + 1;
                }
            }

        }

        return false;
    }

}
